The present invention relates generally to wireless communication systems and more particularly to techniques for scheduling data transmissions in wireless code division multiple access (CDMA) systems and other types of wireless systems.
An increasingly important issue in CDMA systems and other types of wireless systems is scheduling and rate allocation for data transmissions from system base stations to mobile users, i.e., forward link data transmissions. Such systems are moving toward configurations in which mobile users will have heterogenous Quality of Service (QoS) and traffic characteristics. The problem that arises is to how to share resources between mobiles in such a way that their QoS requirements can be effectively met while operating the system with a reasonable level of efficiency. This situation is to be contrasted with that of voice traffic, for which CDMA allows statistical averaging to take place among a large number of delay intolerant users with a common requirement. For data traffic, which is typically more bursty and delay tolerant than voice traffic, scheduling can be used to manage power usage and as a mechanism to control interference.
A conventional scheduling approach used in wired systems is referred to as Generalised Processor Sharing (GPS), and is described in greater detail in, e.g., G. Kesidis, xe2x80x9cATM Network Performance,xe2x80x9d Kluwer, Boston, Mass., 1996, S. Keshav, xe2x80x9cAn Engineering Approach to Computer Networking,xe2x80x9d Addison Wesley, Reading, Mass., 1997, D. Stiliadis and A. Varma, xe2x80x9cRate Proportional Servers: A Design Methodology for Fair Queuing Algorithms,xe2x80x9d IEEE/ACM Trans. Networking, 6:164-174, April 1998, and D. Stiliadis and A. Varma, xe2x80x9cEfficient Fair Queuing Algorithms for Packet Switched Networks,xe2x80x9d IEEE/ACM Trans. Networking, 6:175-185, April 1998, all of which are incorporated by reference herein. The GPS approach converts user QoS requirements into a minimal rate assignment which is provided with high probability, and also provides a Call Admission Control (CAC) framework. The GPS approach is based in part on statistical multiplexing, as described in, e.g., A. Elwalid and D. Mitra, xe2x80x9cDesign of Generalized Processor Sharing Schedulers which Statistically Multiplex Heterogeneous QoS Classes,xe2x80x9d Proc. of IEEE INFOCOM""99, March 1999, pp. 1220-1230, and A. Elwalid, D. Mitra, and R. H. Wentworth. xe2x80x9cA New Approach for Allocating Buffers and Bandwidth to Heterogenous, Regulated Traffic in an ATM Node,xe2x80x9d IEEE Journal on Selected Areas in Communications, 13(6): 1115-1127, August 1995, both of which are incorporated by reference herein.
Despite the advantages provided by the GPS approach in wired systems, the approach is not readily applicable to wireless systems due to wireless-specific complications such as power control and user interference. Therefore, what is needed is an improved approach for scheduling data transmissions in CDMA systems and other types of wireless systems.
The invention provides methods and apparatus for scheduling data transmissions in CDMA systems and other types of wireless communication systems.
In accordance with the invention, the scheduling of data transmissions in a CDMA system or other type of wireless communication system is implemented using a rate processor sharing approach. This approach converts user Quality of Service (QoS) requirements for forward link data transmission into a rate and a corresponding violation probability, and then divides an available system resource such as transmission power among the users in accordance with the rates. For example, the approach may determine for each user i a rate Ri to be provided for user i with a probability 1xe2x88x92exe2x88x92xcex4i, where the xcex4i may be determined independently for each of the users. The system resource may be divided among the users in a manner which satisfies a linear relationship involving the rates and corresponding cost factors of the users. The portion of the system resource allocated to a given user may be fixed for a designated scheduling interval.
In accordance with another aspect of the invention, statistical multiplexing gain may be provided for applications involving multiple bursty users by generating a characterization of the forward link data transmission activity xcex1i of each user i. The activity factor xcex1i denotes the fraction of time the user i actually uses its assigned portion of the system resource. The activity factor xcex1i is a function of the rate Ri of the user i, which is preferably selected to be between a peak rate and a mean data rate for the user i. A queuing model may be used to determine a minimum rate Ri and corresponding activity factor xcex1i that would meet the QoS requirement of user i with a high target probability.
In accordance with another aspect of the invention, an admission control function is provided in which an exact computation or a Chernoff bound approximation is utilized to determine rate violation probabilities for each of the users. The admission control function ensures that a given one of the users is admitted to utilize a portion of the available system resource only if its corresponding rate violation probability meets one or more established criteria.
Advantageously, the rate processor sharing approach of the present invention provides a robust means of system resource sharing in which users with heterogenous QoS requirements can be efficiently supported.